#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
class NumMatrix
{
public:
    NumMatrix(vector<vector<int>> &matrix) : matrix(matrix), IntegerMap(matrix)
    {
        //第一行
        for (int i = 1; IntegerMap.size() > 0 && i < IntegerMap[0].size(); ++i)
            IntegerMap[0][i] += IntegerMap[0][i - 1];
        //第一列
        for (int i = 1; i < IntegerMap.size(); ++i)
            IntegerMap[i][0] += IntegerMap[i - 1][0];
        for (int i = 1; i < IntegerMap.size(); ++i)
        {
            for (int j = 1; IntegerMap.size() > 0 && j < IntegerMap[0].size(); ++j)
            {
                IntegerMap[i][j] += IntegerMap[i - 1][j] + IntegerMap[i][j - 1] - IntegerMap[i - 1][j - 1];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2)
    {
        int A = IntegerMap[row2][col2],
            B = col1 - 1 >= 0 ? IntegerMap[row2][col1 - 1] : 0,
            C = row1 - 1 >= 0 ? IntegerMap[row1 - 1][col2] : 0,
            D = row1 - 1 >= 0 && col1 - 1 >= 0 ? IntegerMap[row1 - 1][col1 - 1] : 0;
        return A - B - C + D;
    }

private:
    vector<vector<int>> IntegerMap, matrix;
};